public class Tree {
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }

        //翻转二叉树
        public TreeNode invertTree(TreeNode root) {

            if (root == null) {
                return null;
            }
            TreeNode tmp = root.left;
            root.left = root.right;
            root.right = tmp;

            invertTree(root.left);
            invertTree(root.right);
            return root;
        }

        public boolean isSameTree(TreeNode p, TreeNode q) {
            //一个为空，一个不为空
            if ((p == null && q != null) || (p != null && q == null)) {
                return false;
            }
            //都为空
            if (p == null && q == null) {
                return true;
            }
            if (p.val != q.val) {
                return false;
            }
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

        }

        //判断是不是另一个树的子树
        public boolean isSubtree(TreeNode root, TreeNode subRoot) {
            if (root == null) {
                return false;
            }
            if (isSameTree(root, subRoot)) {
                return true;
            }
            if (isSubtree(root.left, subRoot)) {
                return true;
            }
            if (isSubtree(root.right, subRoot)) {
                return true;
            }
            return false;
        }
//对称二叉树
        public boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetric2(root.left, root.right);
        }

        public boolean isSymmetric2(TreeNode leftTree, TreeNode rightTree) {
            if ((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)) {
                return false;
            }
            if (leftTree == null && rightTree == null) {
                return true;
            }
            if (leftTree.val != rightTree.val) {
                return false;
            }
            return isSymmetric2(leftTree.left, rightTree.right) && isSymmetric2(leftTree.right, rightTree.left);
        }
//        public boolean isBalanced(TreeNode root) {
//            if(root == null){
//                return true;
//            }
//            int leftH = getHigh(root.left);
//            int rightH = getHigh(root.right);
//            return Math.abs(leftH - rightH)<=1 && isBalanced(root.left) && isBalanced(root.right);
//        }
//        public int getHigh(TreeNode root){
//            if(root == null){
//                return 0;
//            }
//            int leftH = getHigh(root.left);
//            int rightH = getHigh(root.right);
//            return leftH > rightH ? leftH+1 : rightH+1;
//        }
        public boolean isBalanced(TreeNode root) {
           if(root == null){
                return true;
            }
            return getHigh(root) >= 0;
        }
        public int getHigh(TreeNode root){
            if(root == null){
                return 0;
            }
            int leftH = getHigh(root.left);
            if(leftH < 0){
                return -1;
            }
            int rightH = getHigh(root.right);
            if(leftH >= 0 && rightH >= 0 && Math.abs(leftH - rightH)<=1){
                return leftH > rightH ? leftH+1 : rightH+1;
            }else {
                return -1;
            }
        }
    }
}
